/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	include/tree.h
 * @brief 
 *      Tree module, A basic datastruct module.
 *      Memory-free operations, generic frame of tree datastructs
 *      -1. search tree
 *	      -RB-tree, splay-tree, SBT-tree, treap,
 *	      -radix-tree, B+-tree, merkle-tree
 *      -2. space partition tree
 *	      -D-tree, R-tree, Octree, Quad-tree
 *
 * @module      dlib
 * @see		dlib
 *
 * @history
 *		version 0.1.0, spark init tree module with rbtree 
 *		version 0.2.0, spark add splay tree and sbt tree
 *		version 0.3.0, spark add radix tree
 */

#ifndef _DLIB_TREE_H
#define _DLIB_TREE_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"

#ifndef _DLIB_NO_RBTREE
/**
 * Red-Black tree model
 * a binary tree model
 * In linux kernel, rbtree use parent-color var to store parent and color,
 * and employ __attribute__((aligned(sizeof(long)))) to save kernel space.
 */
typedef struct rb_head rbtree_head_t;
typedef struct rb_node rbtree_node_t;

/**
 * rb_compare_fn, key-compare function for insert and find.
 * @return (one to two) 0 equal, -1 little, 1 great.
 */
typedef int (*rb_compare_fn)(const void *one, const void *two);
/**
 * rb_walker_fn, travel function when in/post/preorder rbtree. 
 */
typedef void (*rb_walker_fn)(rbtree_node_t *node, void *arg);

typedef enum {
	RB_RED = 0,
	RB_BLACK
} rb_color_t;

typedef enum {
	RB_EXACT = 1,		/** if key exist, insert return -ERR_ITEM_EXIST */
	RB_OBSCURE		/** insert allow multi-key */
} rb_strategy_t;

typedef enum {
	RB_SEARCH_EQ = 1,	/** equal find */
	RB_SEARCH_LE,		/** little or equal find */
	RB_SEARCH_GE		/** great or equal find */
} rb_search_t;

struct rb_node {
	rbtree_node_t	*left;
	rbtree_node_t	*right;
	rbtree_node_t	*parent;
	rb_color_t	color;
#ifdef _DLIB_RBTREE_SIZE
	uint32_t	size;
#endif
};

struct rb_head {
	rbtree_node_t	*rb_root;
/** compare function */
	rb_compare_fn	rb_compare;
/**
 * the pointer-span between node->node_member and node->key
 * just do:
 * head->key_space = rb_node_entry->pointer_member - rb_node_entry->pointer_key
 */
	long		key_space;
/**
 * the pointer-span between node->value and node->node_member
 * just do:
 * head->value_space = rb_node_entry->pointer_member -
 *	 rb_node_entry->pointer_value
 */
	long		value_space;
};

/** global node rb_leaf for stored only once */
extern rbtree_node_t rb_leaf;

#define RB_HEAD_INIT(compare, ks, vs) \
	{.rb_root = &rb_leaf, \
	 .rb_compare = compare, \
	 .key_space = ks, \
	 .value_space = vs }
#define RB_HEAD(name, compare, ks, vs) \
	rbtree_head_t name = RB_HEAD_INIT(compare, ks, vs)

#define INIT_RB_HEAD(head, compare, ks, vs) \
	({(head)->rb_root =&rb_leaf; \
	  (head)->rb_compare = compare; \
	  (head)->key_space = ks; \
	  (head)->value_space = vs;})

#ifdef _DLIB_RBTREE_SIZE
#define INIT_RB_NODE(node, p, c) \
	({(node)->left = &rb_leaf; \
	  (node)->right = &rb_leaf; \
	  (node)->parent = p; \
	  (node)->color = c; \
	  (node)->size = 1;})
#else
#define INIT_RB_NODE(node, p, c) \
	({(node)->left = &rb_leaf; \
	  (node)->right = &rb_leaf; \
	  (node)->parent = p; \
	  (node)->color = c;})
#endif

#define RB_ROOT(head)		((head)->rb_root)
#define RB_COMPARE(head)	((head)->rb_compare)
#define RB_EMPTY(head)		(RB_ROOT(head) == &rb_leaf)

#define RB_LEFT(node)		((node)->left)
#define RB_RIGHT(node)		((node)->right)
#define RB_PARENT(node)		((node)->parent)
#define RB_COLOR(node)		((node)->color)

#ifdef _DLIB_RBTREE_SIZE
#define RB_SIZE(node)		((node)->size)
#endif

#define RB_IS_RED(node)		(!RB_COLOR(node))
#define RB_IS_BLACK(node)	(RB_COLOR(node))

#ifdef _DLIB_RBTREE_SIZE
#define RB_SET(node, left, right, parent, color, size)	do { \
	RB_PARENT(node) = parent; \
	RB_LEFT(node) = left; \
	RB_RIGHT(node) = right; \
	RB_COLOR(node) = color; \
	RB_SIZE(node) = size;} while (0)
#else
#define RB_SET(node, left, right, parent, color)	do { \
	RB_PARENT(node) = parent; \
	RB_LEFT(node) = left; \
	RB_RIGHT(node) = right; \
	RB_COLOR(node) = color;} while (0)
#endif

#define RB_SET_RED(node)	(RB_COLOR(node) &= ~1)
#define RB_SET_BLACK(node)	(RB_COLOR(node) |= 1)
#define RB_SET_LEFT(node, left)		(RB_LEFT(node) = left)
#define RB_SET_RIGHT(node, right)	(RB_RIGHT(node) = right)
#define RB_SET_PARENT(node, parent)	(RB_PARENT(node) = parent)

#ifdef _DLIB_RBTREE_SIZE
#define RB_SET_SIZE(node, size)	(RB_SIZE(node) = size)
#endif

/* entry operation */
#define RB_ENTRY(node, type, member) \
	((node) == NULL ? NULL: container_of(node, type, member))
#define RB_ROOT_ENTRY(head, type, member) \
	((head)->rb_root == NULL ? NULL : \
		container_of((head)->rb_root, type, member))

/**
 * RB-tree apis, init for a tree with a head, exit for destroy a tree.
 * minimum, maximum, predecessor, successor, insert, delete, find, travel
 */

/**
 * rb_init.
 * @brief init a red-black tree.
 * @param head,tree-head.
 * @param compare_fn,compare function
 * @param key_space,the pointer-span between node->node_member and node->key
 * @param value_space,the pointer-span between node->node_member and node->value
 */
extern int rb_init(rbtree_head_t *head, rb_compare_fn compare_fn,
		   long key_space, long value_space);

/**
 * rb_exit.
 * @brief destroy a red-black tree.
 * @param head,tree-head.
 * @param rb_free_node,free_node function
 * @param arg,free_node function parameters
 */
extern void rb_exit(rbtree_head_t *head, rb_walker_fn rb_free_node, void *arg);

/**
 * rb_minimum.
 * @brief find the minimum key node of a sub-tree.
 * @param node,from which node
 */
extern rbtree_node_t *rb_minimum(rbtree_node_t *node);

/**
 * rb_maximum.
 * @brief find the maximum key node of a sub-tree.
 * @param node,from which node
 */
extern rbtree_node_t *rb_maximum(rbtree_node_t *node);

/**
 * rb_predecessor.
 * @brief find the predecessor key node of a sub-tree.
 * @param node,from which node
 */
extern rbtree_node_t *rb_predecessor(rbtree_node_t *node);

/**
 * rb_successor.
 * @brief find the successor key node of a sub-tree.
 * @param node,from which node
 */
extern rbtree_node_t *rb_successor(rbtree_node_t *node);

#ifdef _DLIB_RBTREE_SIZE
/**
 * rb_select.
 * @brief find the i-th bigger node of a sub-tree.
 * @param node,from which node
 * @param i,the i-th bigger
 */
extern rbtree_node_t *rb_select(rbtree_node_t *node, uint32_t i);

/* rb_rank.
 * @brief find a node's position in a sub-tree.
 * @param from,from which node
 * @param node,the candidate node
 */
extern uint32_t rb_rank(rbtree_node_t *from, rbtree_node_t *node);

/* rb_revrank.
 * @brief find a node's position in a sub-tree.
 * @param from: from which node
 * @param node: the candidate node
 */
extern uint32_t rb_revrank(rbtree_node_t *from, rbtree_node_t *node);
#endif

/**
 * rb_insert.
 * @brief insert a node into rb-tree.
 * @param head: rb-tree head
 * @param node: new node
 * @param strategy: insert strategy, exactly or obscurely
 */
extern int rb_insert(rbtree_head_t *head, rbtree_node_t *node,
		     rb_strategy_t strategy);

/**
 * rb_delete.
 * @brief delete a node from rb-tree.
 * @param head: rb-tree head
 * @param node: new node
 */
extern rbtree_node_t *rb_delete(rbtree_head_t *head, rbtree_node_t *node);

/**
 * rb_find.
 * @brief find a node from rb-tree by a key.
 * @param head: rb-tree head
 * @param node: new node
 * @param cmd: find cmd (seems to be a little complex)
 * @param key: 
 */
extern rbtree_node_t *rb_find(rbtree_head_t * head, rbtree_node_t * node,
			      rb_search_t cmd, void *key);

/**
 * rb_inorder.
 * @brief inorder traver a rb-tree.
 * @param head: rb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int rb_inorder(rbtree_head_t *head, rb_walker_fn walker, void *arg);

/**
 * rb_postorder.
 * @brief postorder traver a rb-tree.
 * @param head: rb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int rb_postorder(rbtree_head_t *head, rb_walker_fn walker, void *arg);

/**
 * rb_preorder.
 * @brief preorder traver a rb-tree.
 * @param head: rb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int rb_preorder(rbtree_head_t *head, rb_walker_fn walker, void *arg);

/* rb-tree OVER */
#endif


#ifndef _DLIB_NO_SPLAYTREE
/**
 * Splay tree model
 * top-down splay implemetation
 */
typedef enum {
	SP_EXACT = 1,		/** if key exist, insert return -ERR_ITEM_EXIST */
	SP_OBSCURE		/** insert allow multi-key */
} sp_strategy_t;

typedef struct splay_node sptree_node_t;
typedef struct splay_head sptree_head_t;

/**
 * sp_compare_fn, key-compare function for insert and find.
 * @return value: (one to two) 0 equal, -1 little, 1 great.
 */
typedef int (*sp_compare_fn)(const void *one, const void *two);
/**
 * sp_walker_fn, travel function when in/post/preorder sptree. 
 */
typedef void (*sp_walker_fn)(sptree_node_t *node, void *arg);

struct splay_node {
	sptree_node_t	*left;
	sptree_node_t	*right;
};

struct splay_head {
	sptree_node_t	*sp_root;
/** compare function */
	sp_compare_fn	sp_compare;
/**
 * the pointer-span between node->node_member and node->key
 * just do:
 * head->key_space = sp_node_entry->pointer_member - sp_node_entry->pointer_key
 */
	long		key_space;
/**
 * the pointer-span between node->value and node->node_member
 * just do:
 * head->value_space = sp_node_entry->pointer_member -
 *	 sp_node_entry->pointer_value
 */
	long		value_space;
#ifdef _DEBUG
/** splay tree nodes count */
	uint32_t	sp_count;
#endif
};

/** sp_leaf assigned to be NULL, accord to rb_leaf */
#define sp_leaf	    NULL

#define SP_HEAD_INIT(compare, ks, vs) \
	{.sp_root = NULL, \
	 .sp_compare = compare, \
	 .key_space = ks, \
	 .value_space = vs }
#define SP_HEAD(name, compare, ks, vs) \
	sptree_head_t name = SP_HEAD_INIT(compare, ks, vs)

#define INIT_SP_HEAD(head, compare, ks, vs) \
	({(head)->sp_root = NULL; \
	  (head)->sp_compare = compare; \
	  (head)->key_space = ks; \
	  (head)->value_space = vs;})

#define INIT_SP_NODE(node) \
	({(node)->left = NULL; \
	  (node)->right = NULL;})

#define SP_ROOT(head)		((head)->sp_root)
#ifdef _DEBUG
#define SP_COUNT(head)		((head)->sp_count)
#endif
#define SP_COMPARE(head)	((head)->sp_compare)
#define SP_EMPTY(head)		(SP_ROOT(head) == NULL)

#define SP_LEFT(node)		((node)->left)
#define SP_RIGHT(node)		((node)->right)

#define SP_SET(node, left, right)	do { \
	SP_LEFT(node) = left; \
	SP_RIGHT(node) = right;} while (0)

#define SP_SET_LEFT(node, left)		(SP_LEFT(node) = left)
#define SP_SET_RIGHT(node, right)	(SP_RIGHT(node) = right)

/** entry operation */
#define SP_ENTRY(node, type, member) \
	((node) == NULL ? NULL: container_of(node, type, member))
#define SP_ROOT_ENTRY(head, type, member) \
	((head)->sp_root == NULL ? NULL : \
		container_of((head)->sp_root, type, member))

/**
 * sp-tree apis, init for a tree with a head, exit for destroy a tree.
 * minimum, maximum, insert, delete, find, travel
 */

/**
 * sp_init.
 * @brief init a splay tree.
 * @param head: tree-head.
 * @param compare_fn: compare function
 * @param key_space: the pointer-span between node->node_member and node->key
 * @param value_space: the pointer-span between node->node_member and node->value
 */
extern int sp_init(sptree_head_t *head, sp_compare_fn compare_fn,
		   long key_space, long value_space);

/**
 * sp_exit.
 * @brief destroy a red-black tree.
 * @param head: tree-head.
 * @param sp_free_node: free_node function
 * @param arg: free_node function parameters
 */
extern void sp_exit(sptree_head_t *head, sp_walker_fn sp_free_node, void *arg);

/**
 * sp_minimum.
 * @brief find the minimum key node of a sub-tree.
 * @param node: from which node
 */
extern sptree_node_t *sp_minimum(sptree_node_t *node);

/**
 * sp_maximum.
 * @brief find the maximum key node of a sub-tree.
 * @param node: from which node
 */
extern sptree_node_t *sp_maximum(sptree_node_t *node);

/**
 * sp_insert.
 * @brief insert a node into sp-tree.
 * @param head: sp-tree head
 * @param node: new node
 * @param strategy: insert strategy, exactly or obscurely
 */
extern int sp_insert(sptree_head_t *head, sptree_node_t *node,
		     sp_strategy_t strategy);

/**
 * sp_delete.
 * @brief delete a node from sp-tree.
 * @param head: sp-tree head
 * @param node: new node
 */
extern sptree_node_t *sp_delete(sptree_head_t *head, sptree_node_t *node);

/**
 * sp_find.
 * @brief find a node from sp-tree by a key.
 * @param head: sp-tree head
 * @param node: new node
 * @param key: key to be found
 */
extern sptree_node_t *sp_find(sptree_head_t *head, sptree_node_t *node,
			      void *key);

/**
 * sp_inorder.
 * @brief inorder traver a sp-tree.
 * @param head: sp-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sp_inorder(sptree_head_t *head, sp_walker_fn walker, void *arg);

/**
 * sp_postorder.
 * @brief postorder traver a sp-tree.
 * @param head: sp-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sp_postorder(sptree_head_t *head, sp_walker_fn walker, void *arg);

/**
 * sp_preorder.
 * @brief preorder traver a sp-tree.
 * @param head: sp-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sp_preorder(sptree_head_t *head, sp_walker_fn walker, void *arg);
/* end splay tree */
#endif


#ifndef _DLIB_NO_SBTREE
/**
 * SBT tree model
 * size balance tree, rank and select operations built-in
 */
typedef struct sb_head sbtree_head_t;
typedef struct sb_node sbtree_node_t;

/**
 * sb_compare_fn, key-compare function for insert and find.
 * @return value: (one to two) 0 equal, -1 little, 1 great.
 */
typedef int (*sb_compare_fn)(const void *one, const void *two);
/**
 * sb_walker_fn, travel function when in/post/preorder sbtree. 
 */
typedef void (*sb_walker_fn)(sbtree_node_t *node, void *arg);

typedef enum {
	SB_EXACT = 1,		/** if key exist, insert return -ERR_ITEM_EXIST */
	SB_OBSCURE		/** insert allow multi-key */
} sb_strategy_t;

struct sb_node {
	sbtree_node_t	*left;
	sbtree_node_t	*right;
	sbtree_node_t	*parent;
	uint32_t	size;
};

struct sb_head {
	sbtree_node_t	*sb_root;
/** compare function */
	sb_compare_fn	sb_compare;
/**
 * the pointer-span between node->node_member and node->key
 * just do:
 * head->key_space = sb_node_entry->pointer_member - sb_node_entry->pointer_key
 */
	long		key_space;
/**
 * the pointer-span between node->value and node->node_member
 * just do:
 * head->value_space = sb_node_entry->pointer_member -
 *	 sb_node_entry->pointer_value
 */
	long		value_space;

#ifdef _DEBUG
/** the nodes count in sbtree */
	uint32_t	sb_count;
#endif
};

/* like rbtree settings */
extern sbtree_node_t sb_leaf;

#define SB_HEAD_INIT(compare, ks, vs) \
	{.sb_root = &sb_leaf, \
	 .sb_compare = compare, \
	 .key_space = ks, \
	 .value_space = vs }
#define SB_HEAD(name, compare, ks, vs) \
	sbtree_head_t name = SB_HEAD_INIT(compare, ks, vs)

#define INIT_SB_HEAD(head, compare, ks, vs) \
	({(head)->sb_root = &sb_leaf; \
	  (head)->sb_compare = compare; \
	  (head)->key_space = ks; \
	  (head)->value_space = vs;})

#define INIT_SB_NODE(node) \
	({(node)->left = &sb_leaf; \
	  (node)->right = &sb_leaf; \
	  (node)->parent = &sb_leaf; \
	  (node)->size = 1;})

#define SB_ROOT(head)		((head)->sb_root)
#define SB_COMPARE(head)	((head)->sb_compare)
#define SB_EMPTY(head)		(SB_ROOT(head) == &sb_leaf)
#ifdef _DEBUG
#define SB_COUNT(head)		((head)->sb_count)
#endif

#define SB_LEFT(node)		((node)->left)
#define SB_RIGHT(node)		((node)->right)
#define SB_PARENT(node)		((node)->parent)
#define SB_SIZE(node)		((node)->size)

#define SB_SET(node, left, right, parent, size)	do { \
	SB_LEFT(node) = left; \
	SB_RIGHT(node) = right; \
	SB_PARENT(node) = parent; \
	SB_SIZE(node) = size; } while (0)

#define SB_SET_LEFT(node, left)		(SB_LEFT(node) = left)
#define SB_SET_RIGHT(node, right)	(SB_RIGHT(node) = right)
#define SB_SET_PARENT(node, parent)	(SB_PARENT(node) = parent)
#define SB_SET_SIZE(node, size)		(SB_SIZE(node) = size)

/** entry operation */
#define SB_ENTRY(node, type, member) \
	(((node) == NULL || (node) == &sb_leaf) ? NULL: container_of(node, type, member))
#define SB_ROOT_ENTRY(head, type, member) \
	(((head)->sb_root == NULL || (head)->sb_root == &sb_leaf) ? NULL : \
		container_of((head)->sb_root, type, member))

/**
 * SB-tree apis, init for a tree with a head, exit for destroy a tree.
 * minimum, maximum, predecessor, successor, insert, delete, find, travel
 */

/**
 * sb_init.
 * @brief init a size-balanced tree.
 * @param head,tree-head.
 * @param compare_fn,compare function
 * @param key_space,the pointer-span between node->node_member and node->key
 * @param value_space,the pointer-span between node->node_member and node->value
 */
extern int sb_init(sbtree_head_t *head, sb_compare_fn compare_fn,
		   long key_space, long value_space);
/**
 * sb_exit.
 * @brief destroy a size-balanced tree.
 * @param head: tree-head.
 * @param sb_free_node: free_node function
 * @param arg: free_node function parameters
 */
extern void sb_exit(sbtree_head_t *head, sb_walker_fn sb_free_node, void *arg);

/**
 * sb_minimum.
 * @brief find the minimum key node of a sub-tree.
 * @param node: from which node
 */
extern sbtree_node_t *sb_minimum(sbtree_node_t *node);

/**
 * sb_maximum.
 * @brief find the maximum key node of a sub-tree.
 * @param node: from which node
 */
extern sbtree_node_t *sb_maximum(sbtree_node_t *node);

/**
 * sb_predecessor.
 * @brief find the predecessor key node of a sub-tree.
 * @param node: from which node
 */
extern sbtree_node_t *sb_predecessor(sbtree_node_t *node);

/**
 * sb_successor.
 * @brief find the successor key node of a sub-tree.
 * @param node: from which node
 */
extern sbtree_node_t *sb_successor(sbtree_node_t *node);

/**
 * sb_select.
 * @brief find the i-th bigger node of a sub-tree.
 * @param node: from which node
 * @param i: the i-th bigger
 */
extern sbtree_node_t *sb_select(sbtree_node_t *node, uint32_t i);

/**
 * sb_rank.
 * @brief find a node's position in a sub-tree.
 * @param from: from which node
 * @param @node: the candidate node
 */
extern uint32_t sb_rank(sbtree_node_t *from, sbtree_node_t *node);

/**
 * sb_revrank.
 * @brief find a node's position in a sub-tree.
 * @param from: from which node
 * @param node: the candidate node
 */
extern uint32_t sb_revrank(sbtree_node_t *from, sbtree_node_t *node);

/**
 * sb_insert.
 * @brief insert a node into sb-tree.
 * @param head: sb-tree head
 * @param node: new node
 * @param strategy: insert strategy, exactly or obscurely
 */
extern int sb_insert(sbtree_head_t *head, sbtree_node_t *node,
		     sb_strategy_t strategy);

/**
 * sb_delete.
 * @brief delete a node from sb-tree.
 * @param head: sb-tree head
 * @param node: new node
 */
extern sbtree_node_t *sb_delete(sbtree_head_t *head, sbtree_node_t *node);

/**
 * sb_find.
 * @brief find a node from sb-tree by a key.
 * @param head: sb-tree head
 * @param node: new node
 * @param key: 
 */
extern sbtree_node_t *sb_find(sbtree_head_t * head, sbtree_node_t * node,
			      void *key);
/**
 * sb_inorder.
 * @brief inorder traver a sb-tree.
 * @param head: sb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sb_inorder(sbtree_head_t *head, sb_walker_fn walker, void *arg);

/**
 * sb_postorder.
 * @brief postorder traver a sb-tree.
 * @param head: sb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sb_postorder(sbtree_head_t *head, sb_walker_fn walker, void *arg);

/**
 * sb_preorder.
 * @brief preorder traver a sb-tree.
 * @param head: sb-tree head
 * @param walker: walker function
 * @param arg: find cmd (seems to be a little complex)
 */
extern int sb_preorder(sbtree_head_t *head, sb_walker_fn walker, void *arg);
/** end size balance tree */
#endif


#ifndef _DLIB_NO_TREAP
/**
 * Treap model
 * dynamic adjust treap weight
 */


#endif



#ifndef _DLIB_NO_RADIX
/**
 * Radix tree model
 * a adjustable radix-tree model
 */


#endif


#ifndef _DLIB_NO_MERKLE
/**
 * merkle tree model
 * hash tree for exchange large sum of data
 */


#endif


#ifndef _DLIB_NO_BTREE
/**
 * B+ tree model
 * generate B tree model
 */


#endif


#ifdef __cplusplus
}
#endif
#endif
